{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #BiNode LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Easy"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #LCCI"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #stack #tree #depth-first-search #binary-search-tree #linked-list #binary-tree"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #栈 #树 #深度优先搜索 #二叉搜索树 #链表 #二叉树"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: convertBiNode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #BiNode"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>二叉树数据结构<code>TreeNode</code>可用来表示单向链表（其中<code>left</code>置空，<code>right</code>为下一个链表节点）。实现一个方法，把二叉搜索树转换为单向链表，要求依然符合二叉搜索树的性质，转换操作应是原址的，也就是在原始的二叉搜索树上直接修改。</p>\n",
    "\n",
    "<p>返回转换后的单向链表的头节点。</p>\n",
    "\n",
    "<p><strong>注意：</strong>本题相对原题稍作改动</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例：</strong></p>\n",
    "\n",
    "<pre><strong>输入：</strong> [4,2,5,1,3,null,6,0]\n",
    "<strong>输出：</strong> [0,null,1,null,2,null,3,null,4,null,5,null,6]\n",
    "</pre>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li>节点数量不会超过 100000。</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [binode-lcci](https://leetcode.cn/problems/binode-lcci/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [binode-lcci](https://leetcode.cn/problems/binode-lcci/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[4,2,5,1,3,null,6,0]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre=self.ans=None\n",
    "        def dfs(root):\n",
    "            if not root :return\n",
    "            dfs(root.left)\n",
    "            root.left=None\n",
    "            if self.pre:self.pre.right=root\n",
    "            if self.pre is None:self.ans=root\n",
    "            self.pre=root\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        if root.left is None:\n",
    "            new_root = root\n",
    "        else:\n",
    "            new_root = self.convertBiNode(root.left)\n",
    "            temp = new_root\n",
    "            while temp.right is not None:\n",
    "                temp = temp.right\n",
    "            temp.right = root\n",
    "            root.left = None\n",
    "        if root.right is not None:\n",
    "            root.right = self.convertBiNode(root.right)\n",
    "        return new_root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        def inorder(node):\n",
    "            if node:\n",
    "                inorder(node.left)\n",
    "                node.left = None\n",
    "                self.cur.right = node\n",
    "                self.cur = node\n",
    "                inorder(node.right)\n",
    "        \n",
    "        self.ans = self.cur = TreeNode(None)\n",
    "        inorder(root)\n",
    "        return self.ans.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def walk(self, node):\n",
    "        if node:\n",
    "            self.t.append(node)\n",
    "            self.walk(node.left)\n",
    "            self.walk(node.right)\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        t = []\n",
    "        self.t = t\n",
    "        self.walk(root)\n",
    "        self.t.sort(key = lambda k:k.val)\n",
    "\n",
    "        # print(t)\n",
    "\n",
    "        for i in range(len(t)-1):\n",
    "            t[i].left = None\n",
    "            t[i].right = t[i+1]\n",
    "        \n",
    "        if len(t)>0:\n",
    "            t[-1].left = None\n",
    "            t[-1].right = None\n",
    "            return t[0]\n",
    "        else:\n",
    "            return None"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre=self.ans=None\n",
    "        def dfs(root):\n",
    "            if not root:return\n",
    "            dfs(root.left)\n",
    "            root.left=None\n",
    "            if self.pre:self.pre.right=root\n",
    "            if self.pre is None:self.ans=root\n",
    "            self.pre=root\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.head = TreeNode(0) # 初始化一个结点head，head的右节点是该树的最小子节点\n",
    "        self.ans = self.head # 存储head的起始位置，随后递归时head的位置会从小到大依次出现在二叉树的每一个节点上\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        # 中序遍历递归的一般终止条件\n",
    "        if not root:\n",
    "            return None\n",
    "        # 先搜索左树\n",
    "        self.convertBiNode(root.left)\n",
    "        # 核心思想：结点的左子树清空，只留右子树，由于中序遍历会递归至最左的叶结点上开始计算，因此每次计算结束时该节点的左子树已被转移至head.right上，因此不会出现丢失的情况\n",
    "        root.left = None\n",
    "        self.head.right = root\n",
    "        self.head = self.head.right\n",
    "\n",
    "        # 再搜索右树\n",
    "        self.convertBiNode(root.right)\n",
    "\n",
    "        # 起始结点为初始的head.right\n",
    "        return self.ans.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.head = TreeNode(0) # 初始化一个结点head，head的右节点是该树的最小子节点\n",
    "        self.ans = self.head # 存储head的起始位置，随后递归时head的位置会从小到大依次出现在二叉树的每一个节点上\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        # 中序遍历递归的一般终止条件\n",
    "        if not root:\n",
    "            return None\n",
    "        # 先搜索左树\n",
    "        self.convertBiNode(root.left)\n",
    "        # 核心思想：结点的左子树清空，只留右子树，由于中序遍历会递归至最左的叶结点上开始计算，因此每次计算结束时该节点的左子树已被转移至head.right上，因此不会出现丢失的情况\n",
    "        root.left = None\n",
    "        self.head.right = root\n",
    "        self.head = self.head.right\n",
    "\n",
    "        # 再搜索右树\n",
    "        self.convertBiNode(root.right)\n",
    "\n",
    "        # 起始结点为初始的head.right\n",
    "        return self.ans.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = self.ans = None\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            root.left = None\n",
    "            if self.pre: \n",
    "                self.pre.right = root\n",
    "            if self.pre is None: \n",
    "                self.ans = root\n",
    "            self.pre = root\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "# 作者：lucifer"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return root\n",
    "            \n",
    "        left = self.convertBiNode(root.left)\n",
    "        right = self.convertBiNode(root.right)\n",
    "        root.left = None\n",
    "        root.right = right\n",
    "        if not left:\n",
    "            return root\n",
    "        else:\n",
    "            new_head = left\n",
    "            while left.right:\n",
    "                left = left.right\n",
    "            left.right = root\n",
    "        return new_head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = self.ans = None\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            root.left = None\n",
    "            if self.pre: self.pre.right = root\n",
    "            if self.pre is None: self.ans = root\n",
    "            self.pre = root\n",
    "\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        dummy_head = TreeNode(-1)\n",
    "        prev = dummy_head\n",
    "        def dfs(root):\n",
    "            nonlocal prev\n",
    "            if root:\n",
    "                dfs(root.left)\n",
    "                prev.right = root\n",
    "                root.left = None\n",
    "                prev = root\n",
    "                dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return dummy_head.right\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.treenode = None\n",
    "        def reverseInOrder(root):\n",
    "            if not root:\n",
    "                return None\n",
    "            reverseInOrder(root.right)\n",
    "            root.right = self.treenode \n",
    "            self.treenode = root \n",
    "            reverseInOrder(root.left)\n",
    "            root.left = None\n",
    "            return root \n",
    "        reverseInOrder(root)\n",
    "        return self.treenode"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        dump = TreeNode(-1)\n",
    "        self.root = dump\n",
    "        def dg(root):\n",
    "            if not root:return None\n",
    "            dg(root.left)\n",
    "            self.root.right = root\n",
    "            self.root = self.root.right\n",
    "            self.root.left = None\n",
    "            dg(root.right)\n",
    "        dg(root)\n",
    "        return dump.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None: return None\n",
    "        lroot, rroot = root.left, root.right\n",
    "        \n",
    "        # 处理右子树：把右子树归链\n",
    "        root.right = self.convertBiNode(rroot)\n",
    "        \n",
    "        # 处理左子树：把左子树归链，然后把根节点添到左子树上\n",
    "        if root.left:\n",
    "            pre = root.left\n",
    "            while pre.right is not None:\n",
    "                pre = pre.right\n",
    "            lroot = self.convertBiNode(lroot)\n",
    "            root.left = None\n",
    "            pre.right = root\n",
    "            root = lroot\n",
    "        \n",
    "        return root\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = self.head = None\n",
    "        def inorder(root):\n",
    "            if root is None: return root\n",
    "            inorder(root.left)\n",
    "            root.left = None\n",
    "            if self.pre: self.pre.right = root\n",
    "            self.pre = root\n",
    "            if not self.head: self.head = self.pre\n",
    "            inorder(root.right)\n",
    "        inorder(root)\n",
    "        return self.head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.head = TreeNode(0) # 初始化一个结点head，head的右节点是该树的最小子节点\n",
    "        self.ans = self.head # 存储head的起始位置，随后递归时head的位置会从小到大依次出现在二叉树的每一个节点上\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        # 中序遍历递归的一般终止条件\n",
    "        if not root:\n",
    "            return None\n",
    "        # 先搜索左树\n",
    "        self.convertBiNode(root.left)\n",
    "        # 核心思想：结点的左子树清空，只留右子树，由于中序遍历会递归至最左的叶结点上开始计算，因此每次计算结束时该节点的左子树已被转移至head.right上，因此不会出现丢失的情况\n",
    "        root.left = None\n",
    "        self.head.right = root\n",
    "        self.head = self.head.right\n",
    "\n",
    "        # 再搜索右树\n",
    "        self.convertBiNode(root.right)\n",
    "\n",
    "        # 起始结点为初始的head.right\n",
    "        return self.ans.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.resHead = self.cur = TreeNode(None)\n",
    "    def convert(self,root):\n",
    "        if not root:\n",
    "            return None\n",
    "        self.convert(root.left) #递归\n",
    "        #插入节点，顺序为右侧实数，左侧None\n",
    "        root.left = None\n",
    "        self.cur.right = root\n",
    "        self.cur = root\n",
    "\n",
    "        self.convert(root.right)\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.convert(root)\n",
    "        return self.resHead.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        def recur(root) -> (TreeNode, TreeNode):\n",
    "            if root == None:\n",
    "                return (None, None)\n",
    "            lh, lt, rh, rt = None, None, None, None\n",
    "            if root.left != None:\n",
    "                lh, lt = recur(root.left)\n",
    "            if root.right != None:\n",
    "                rh, rt = recur(root.right)\n",
    "            if lh:\n",
    "                head = lh\n",
    "                lt.right = root\n",
    "                root.left = None\n",
    "                root.right = rh\n",
    "            else:\n",
    "                head = root\n",
    "                root.right = rh\n",
    "            if rt:\n",
    "                tail = rt\n",
    "            else:\n",
    "                tail = root\n",
    "            return (head, tail)\n",
    "        head, _ = recur(root)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        head=TreeNode(None)\n",
    "        pre=head\n",
    "        cur=root\n",
    "        stack=[]\n",
    "        while cur or stack:\n",
    "            while cur:\n",
    "                stack.append(cur)\n",
    "                cur=cur.left\n",
    "            cur=stack.pop()\n",
    "            cur.left=None\n",
    "            pre.right=cur\n",
    "            pre=cur\n",
    "            cur=cur.right\n",
    "        return head.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        head, pre = None, None\n",
    "        while (root != None or\n",
    "               len(stack) > 0):\n",
    "            if root != None:\n",
    "                stack.append(root)\n",
    "                root = root.left\n",
    "            else:\n",
    "                root = stack.pop()\n",
    "                head = root if head == None else head\n",
    "                if pre != None:\n",
    "                    pre.left = None\n",
    "                    pre.right = root\n",
    "                pre = root\n",
    "                root = root.right\n",
    "            if pre != None:\n",
    "                pre.left = None\n",
    "                pre.right = root\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        def convert(root):\n",
    "            begin = end = root\n",
    "            if root:\n",
    "                if root.left:\n",
    "                    begin, end = convert(root.left)\n",
    "                    end.right = root\n",
    "                    root.left = None\n",
    "                    end = root\n",
    "                if root.right:\n",
    "                    root.right, end = convert(root.right)\n",
    "            return begin, end\n",
    "        return convert(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = self.ans = None\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            root.left = None\n",
    "            if self.pre: self.pre.right = root\n",
    "            if self.pre is None: self.ans = root\n",
    "            self.pre = root\n",
    "\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    '''\n",
    "    In-order traversal using recursion. Store the last-reached node as a instance attribute (like a global variable). \n",
    "    Time complexity: O(n). Space complexity: O(height of tree) (from recursion calls). \n",
    "    '''\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        # Method 1: recursive in-order traversal\n",
    "        # def inOrder(node):\n",
    "        #     if not node:\n",
    "        #         return\n",
    "        #     inOrder(node.left)\n",
    "        #     if not self.lastNode:\n",
    "        #         self.head = node\n",
    "        #     else:\n",
    "        #         self.lastNode.right = node\n",
    "        #     node.left = None\n",
    "        #     self.lastNode = node\n",
    "        #     inOrder(node.right)\n",
    "        \n",
    "        # self.head = None\n",
    "        # self.lastNode = None\n",
    "        # inOrder(root)\n",
    "        # return self.head\n",
    "\n",
    "        # Method 2: iterative in-order traversal\n",
    "        s = []\n",
    "        node = root\n",
    "        head = lastNode = None\n",
    "        while s or node:\n",
    "            while node:\n",
    "                s.append(node)\n",
    "                node = node.left\n",
    "            node = s.pop()\n",
    "            if not head:\n",
    "                head = node\n",
    "            else:\n",
    "                lastNode.right = node\n",
    "            node.left = None\n",
    "            lastNode = node\n",
    "            node = node.right\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "      # 中序遍历\n",
    "      ret = None\n",
    "      ret_tmp = None\n",
    "      s = []\n",
    "      r = root\n",
    "      if r == None:\n",
    "        return r\n",
    "      while True:\n",
    "        if r.left:\n",
    "          s.append(r)\n",
    "          r = r.left\n",
    "        elif r.right:\n",
    "          # print(r.val) # 打印右子树\n",
    "          if ret == None:\n",
    "            ret = r\n",
    "            ret_tmp = ret\n",
    "          else:\n",
    "            ret_tmp.right = r\n",
    "            ret_tmp = ret_tmp.right\n",
    "          r = r.right\n",
    "        else:\n",
    "          # print(r.val) # 打印根节点\n",
    "          if ret == None:\n",
    "            ret = r\n",
    "            ret_tmp = ret\n",
    "          else:\n",
    "            ret_tmp.right = r\n",
    "            ret_tmp = ret_tmp.right\n",
    "          if len(s) == 0:\n",
    "            break\n",
    "          r = s.pop()\n",
    "          r.left = None\n",
    "      \n",
    "      return ret\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "        \n",
    "      "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        head=TreeNode(0)\n",
    "        pre=None\n",
    "        def trackback(root):\n",
    "            nonlocal pre\n",
    "            if not root:\n",
    "                return\n",
    "            trackback(root.left)\n",
    "            if not pre:\n",
    "                pre=root\n",
    "                head.right=pre\n",
    "            else:\n",
    "                pre.right=root\n",
    "                pre=pre.right\n",
    "            pre.left=None\n",
    "            trackback(root.right)\n",
    "\n",
    "        trackback(root)\n",
    "        return head.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:return None\n",
    "        left,right = None,None\n",
    "        if root.left:\n",
    "            left = self.convertBiNode(root.left)\n",
    "        if root.right:\n",
    "            right = self.convertBiNode(root.right)\n",
    "        if left:\n",
    "            cur = left\n",
    "            while cur.right:\n",
    "                cur = cur.right\n",
    "            cur.right = root\n",
    "        root.left = None\n",
    "        root.right = right\n",
    "        return left if left else root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convert(self, cur):\n",
    "        if cur is None:\n",
    "            return None, None\n",
    "        if cur.left is None and cur.right is None:\n",
    "            return cur, cur\n",
    "        elif cur.left is None:\n",
    "            rnh, rnt = self.convert(cur.right)\n",
    "            cur.right = rnh\n",
    "            return cur, rnt\n",
    "        elif cur.right is None:\n",
    "            lnh, lnt = self.convert(cur.left)\n",
    "            lnt.right = cur\n",
    "            cur.left = None\n",
    "            return lnh, cur\n",
    "        else:\n",
    "            lnh, lnt = self.convert(cur.left)\n",
    "            rnh, rnt = self.convert(cur.right)\n",
    "            lnt.right = cur\n",
    "            cur.left = None\n",
    "            cur.right = rnh\n",
    "            return lnh, rnt\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        h, t = self.convert(root)\n",
    "        return h"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.head=self.cur=TreeNode(0)\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return None\n",
    "        self.convertBiNode(root.left)\n",
    "        root.left=None\n",
    "        self.head.right=root\n",
    "        self.head=self.head.right\n",
    "        self.convertBiNode(root.right)\n",
    "        return self.cur.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.prev = self.ans = None       \n",
    "        def dfs(node: TreeNode):\n",
    "            if node is None: return\n",
    "            dfs(node.left)\n",
    "            if self.prev is None:\n",
    "                self.ans = node\n",
    "                self.prev = node\n",
    "            else:\n",
    "                node.left = None\n",
    "                self.prev.right = node\n",
    "                self.prev = node                \n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.prev = self.ans = None       \n",
    "        def dfs(node: TreeNode):\n",
    "            if node is None: return\n",
    "            dfs(node.left)\n",
    "            if self.prev is None:\n",
    "                self.ans = node\n",
    "                self.prev = node\n",
    "            else:\n",
    "                node.left = None\n",
    "                self.prev.right = node\n",
    "                self.prev = node                \n",
    "            dfs(node.right)\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        stack = []\n",
    "        head = TreeNode(-1)\n",
    "        t = head\n",
    "\n",
    "        p = root\n",
    "        while p:\n",
    "            stack.append(p)\n",
    "            p = p.left\n",
    "        \n",
    "        while stack:\n",
    "            p1 = stack.pop()\n",
    "            p1.left = None\n",
    "            t.right = p1\n",
    "            t = t.right\n",
    "\n",
    "            r = p1.right\n",
    "            while r:\n",
    "                stack.append(r)\n",
    "                r = r.left\n",
    "        return head.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if not root: \n",
    "            return root\n",
    "\n",
    "        if not root.left and not root.right:\n",
    "            return root\n",
    "        \n",
    "        if not root.left:\n",
    "            head = root       \n",
    "            while root.right and not root.right.left:\n",
    "                root = root.right  \n",
    "            root.right = self.convertBiNode(root.right)\n",
    "            return head\n",
    "        \n",
    "        ret = self.convertBiNode(root.left)\n",
    "        head = ret\n",
    "        if root.right:\n",
    "            root.right = self.convertBiNode(root.right)\n",
    "        root.left = None\n",
    "        while ret.right:\n",
    "            ret = ret.right\n",
    "        ret.right = root\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        pre = ans = None\n",
    "        def dfs(root):\n",
    "            nonlocal pre,ans\n",
    "            if not root:return\n",
    "            dfs(root.left)\n",
    "            root.left = None\n",
    "            if pre:\n",
    "                pre.right = root\n",
    "            if not pre:\n",
    "                ans = root\n",
    "            pre = root\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def _convertBiNode(self, root):\n",
    "        if root.left is None and root.right is None:\n",
    "            return root, root\n",
    "        elif root.left is None:\n",
    "            head, tail = self._convertBiNode(root.right)\n",
    "            root.right = head\n",
    "            return root, tail\n",
    "        elif root.right is None:\n",
    "            head, tail = self._convertBiNode(root.left)\n",
    "            root.left = None\n",
    "            root.right = None\n",
    "            tail.right = root\n",
    "            return head, root\n",
    "        else:\n",
    "            lhead, ltail = self._convertBiNode(root.left)\n",
    "            rhead, rtail = self._convertBiNode(root.right)\n",
    "            root.left = None\n",
    "            root.right = rhead\n",
    "            ltail.right = root\n",
    "            return lhead, rtail\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return root\n",
    "        else:\n",
    "            head, tail = self._convertBiNode(root)\n",
    "            return head\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = None\n",
    "        self.ans = None\n",
    "        def inorder(root):\n",
    "            if not root: return\n",
    "            inorder(root.left)\n",
    "            if self.pre:\n",
    "                self.pre.right = root\n",
    "                root.left = None\n",
    "            elif not self.pre:\n",
    "                self.ans = root\n",
    "            self.pre = root\n",
    "            inorder(root.right)\n",
    "\n",
    "        inorder(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = self.ans = None\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            root.left = None\n",
    "            if self.pre: self.pre.right = root\n",
    "            if self.pre is None: self.ans = root\n",
    "            self.pre = root\n",
    "\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.prev = self.ans = None\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            if not self.prev:\n",
    "                self.ans = root\n",
    "                self.prev = root\n",
    "            else:\n",
    "                self.prev.right = root\n",
    "                self.prev = root\n",
    "            self.prev.left = None\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cur = TreeNode()\n",
    "        self.res = self.cur\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:return None\n",
    "        self.convertBiNode(root.left)\n",
    "        root.left=None\n",
    "        self.cur.right = root\n",
    "        self.cur = self.cur.right\n",
    "        self.convertBiNode(root.right)\n",
    "        return self.res.right\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.head = TreeNode(0) # 初始化一个结点head，head的右节点是该树的最小子节点\n",
    "        self.ans = self.head # 存储head的起始位置，随后递归时head的位置会从小到大依次出现在二叉树的每一个节点上\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        # 中序遍历递归的一般终止条件\n",
    "        if not root:\n",
    "            return None\n",
    "        # 先搜索左树\n",
    "        self.convertBiNode(root.left)\n",
    "        # 核心思想：结点的左子树清空，只留右子树，由于中序遍历会递归至最左的叶结点上开始计算，因此每次计算结束时该节点的左子树已被转移至head.right上，因此不会出现丢失的情况\n",
    "        root.left = None\n",
    "        self.head.right = root\n",
    "        self.head = self.head.right\n",
    "\n",
    "        # 再搜索右树\n",
    "        self.convertBiNode(root.right)\n",
    "\n",
    "        # 起始结点为初始的head.right\n",
    "        return self.ans.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "            # 定义一个辅助函数来进行中序遍历并修改指针\n",
    "        def inorder(node):\n",
    "            nonlocal prev\n",
    "            if node is None:\n",
    "                return\n",
    "            inorder(node.left)\n",
    "            prev.right = node\n",
    "            node.left = None\n",
    "            prev = node\n",
    "            inorder(node.right)\n",
    "\n",
    "        # 创建一个虚拟节点作为链表的头节点\n",
    "        dummy = TreeNode()\n",
    "        prev = dummy\n",
    "\n",
    "        # 进行中序遍历并修改指针\n",
    "        inorder(root)\n",
    "\n",
    "        # 返回链表的头节点\n",
    "        return dummy.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        ans = cur = TreeNode(None)\n",
    "        def inorder(node):\n",
    "            nonlocal cur\n",
    "            if node:\n",
    "                inorder(node.left)\n",
    "                node.left = None\n",
    "                cur.right = node\n",
    "                cur = node\n",
    "                inorder(node.right)\n",
    "        \n",
    "        \n",
    "        inorder(root)\n",
    "        return ans.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        head=TreeNode(0)\n",
    "        pre=None\n",
    "        def trackback(root):\n",
    "            nonlocal pre\n",
    "            if not root:\n",
    "                return\n",
    "            trackback(root.left)\n",
    "            if not pre:\n",
    "                pre=root\n",
    "                head.right=root\n",
    "            else:\n",
    "                pre.right=root\n",
    "                pre=pre.right\n",
    "            pre.left=None\n",
    "            trackback(root.right)\n",
    "\n",
    "        trackback(root)\n",
    "        return head.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = self.ans = None\n",
    "        if root is None:\n",
    "            return\n",
    "        def dfs(root):\n",
    "            if root is None:\n",
    "                return None\n",
    "        \n",
    "            dfs(root.left)\n",
    "            root.left = None\n",
    "            if self.pre: self.pre.right = root\n",
    "            if self.pre is None: self.ans = root\n",
    "            self.pre = root\n",
    "            dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = self.ans = None\n",
    "        if root is None:\n",
    "            return\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, root):\n",
    "            if root is None:\n",
    "                return None\n",
    "        \n",
    "            self.dfs(root.left)\n",
    "            root.left = None\n",
    "            if self.pre: self.pre.right = root\n",
    "            if self.pre is None: self.ans = root\n",
    "            self.pre = root\n",
    "            self.dfs(root.right)\n",
    "\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\r\n",
    "# class TreeNode:\r\n",
    "#     def __init__(self, x):\r\n",
    "#         self.val = x\r\n",
    "#         self.left = None\r\n",
    "#         self.right = None\r\n",
    "\r\n",
    "class Solution:\r\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\r\n",
    "        if root is None: return None\r\n",
    "        lroot, rroot = root.left, root.right\r\n",
    "        \r\n",
    "        # 处理右子树：把右子树归链\r\n",
    "        root.right = self.convertBiNode(rroot)\r\n",
    "        \r\n",
    "        # 处理左子树：把左子树归链，然后把根节点添到左子树上\r\n",
    "        if root.left:\r\n",
    "            pre = root.left\r\n",
    "            while pre.right is not None:\r\n",
    "                pre = pre.right\r\n",
    "            lroot = self.convertBiNode(lroot)\r\n",
    "            root.left = None\r\n",
    "            pre.right = root\r\n",
    "            root = lroot\r\n",
    "        \r\n",
    "        return root\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        def convert(root: TreeNode):\n",
    "            if not root:\n",
    "                return root, root\n",
    "            begin=end=root\n",
    "            if root.left:\n",
    "                begin, end = convert(root.left)\n",
    "                end.right = root\n",
    "                end = root\n",
    "                root.left=None\n",
    "            if root.right:\n",
    "                root.right, end = convert(root.right)\n",
    "            return begin, end\n",
    "        return convert(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if not root: return None \n",
    "        self.cur = self.pre = TreeNode(root.val, None, None)\n",
    "        def dfs(root):\n",
    "            if not root: return \n",
    "            dfs(root.left)\n",
    "            root.left = None \n",
    "            self.cur.right = root\n",
    "            self.cur = root\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.pre.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = self.ans = None\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return \n",
    "            # 中序遍历\n",
    "            dfs(root.left)\n",
    "            root.left = None\n",
    "            if self.pre:\n",
    "                self.pre.right = root\n",
    "            else:\n",
    "                self.ans = root\n",
    "            self.pre = root\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = self.ans = None\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            root.left = None\n",
    "            if self.pre: self.pre.right = root\n",
    "            if self.pre is None: self.ans = root\n",
    "            self.pre = root\n",
    "\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:return None\n",
    "        left,right = None,None\n",
    "        if root.left:\n",
    "            left = self.convertBiNode(root.left)\n",
    "        if root.right:\n",
    "            right = self.convertBiNode(root.right)\n",
    "        if left:\n",
    "            cur = left\n",
    "            while cur.right:\n",
    "                cur = cur.right\n",
    "            cur.right = root\n",
    "        root.left = None\n",
    "        root.right = right\n",
    "        return left if left else root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    # def __init__(self,):\n",
    "    #    self.res = self.head = TreeNode(0)\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        head = TreeNode(0)   \n",
    "        res = head \n",
    "\n",
    "        def dfs(root, ): \n",
    "            nonlocal head \n",
    "            if root is None:\n",
    "                return None \n",
    "            dfs(root.left)\n",
    "            root.left = None\n",
    "            head.right = root \n",
    "            head = head.right \n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return res.right "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        def convert(root):\n",
    "            begin = end = root\n",
    "            if root:\n",
    "                if root.left:\n",
    "                    begin, end = convert(root.left)\n",
    "                    end.right = root\n",
    "                    end = root\n",
    "                    root.left = None\n",
    "                if root.right:\n",
    "                    root.right, end = convert(root.right)\n",
    "            return begin, end\n",
    "        return convert(root)[0]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self,):\n",
    "        self.res = self.head = TreeNode(0)\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        def dfs(root, ): \n",
    "            if root is None:\n",
    "                return None \n",
    "            dfs(root.left)\n",
    "            root.left = None\n",
    "            self.head.right = root \n",
    "            self.head = self.head.right \n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.res.right "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self,):\n",
    "        self.head = TreeNode(None)\n",
    "        self.res = self.head \n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root, ):\n",
    "            if root is None:\n",
    "                return None\n",
    "            dfs(root.left)\n",
    "            root.left = None \n",
    "            self.head.right = root \n",
    "            self.head = self.head.right \n",
    "            dfs(root.right)\n",
    "\n",
    "        dfs(root)\n",
    "        return self.res.right"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.head = self.current = TreeNode(None)   #定义头结点，最后返回头结点的右子节点\n",
    "        self.inOrder(root)\n",
    "        return self.head.right\n",
    "\n",
    "    def inOrder(self, root):\n",
    "        if not root:\n",
    "            return\n",
    "        self.inOrder(root.left)\n",
    "        root.left = None            #当前节点的左子节点置空\n",
    "        self.current.right = root   #上个节点的右子节点赋值为当前节点\n",
    "        self.current = root         #更新当前节点，注意顺序\n",
    "        self.inOrder(root.right)\n",
    "\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        \n",
    "        self.pre = self.ans = None\n",
    "        def dfs(root):\n",
    "            if not root: return\n",
    "            dfs(root.left)\n",
    "            root.left = None\n",
    "            if self.pre: self.pre.right = root\n",
    "\n",
    "            if self.pre is None: self.ans = root\n",
    "            self.pre = root\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.res = self.pre = None\n",
    "        def reverse(root):\n",
    "            if not root:\n",
    "                return\n",
    "            reverse(root.left)\n",
    "            root.left = None\n",
    "            if self.pre:\n",
    "                self.pre.right = root\n",
    "            else:\n",
    "                self.res = root\n",
    "            self.pre = root\n",
    "            reverse(root.right)\n",
    "        \n",
    "        reverse(root)\n",
    "        return self.res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = None\n",
    "        self.root = None\n",
    "\n",
    "        def dfs(root):\n",
    "            if not root:\n",
    "                return\n",
    "            dfs(root.left)\n",
    "            root.left = None\n",
    "            if not self.pre:\n",
    "                self.pre = root\n",
    "                self.root = self.pre\n",
    "            else:\n",
    "                self.pre.right = root\n",
    "                self.pre = self.pre.right\n",
    "            dfs(root.right)\n",
    "        dfs(root)\n",
    "        return self.root"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        def inorder(node, last):\n",
    "            nonlocal first\n",
    "            if not node:\n",
    "                return last\n",
    "\n",
    "            last = inorder(node.left, last)\n",
    "            \n",
    "            if last:\n",
    "                last.right = node\n",
    "            else:\n",
    "                first = node\n",
    "\n",
    "            node.left = None\n",
    "            return inorder(node.right, node)\n",
    "\n",
    "        first = None\n",
    "        inorder(root, None)\n",
    "        return first\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self,):\n",
    "        self.res = self.head = TreeNode(0)\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root, ): \n",
    "            if root is None:\n",
    "                return None \n",
    "            dfs(root.left)\n",
    "            root.left = None \n",
    "            self.head.right = root \n",
    "            self.head = self.head.right \n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.res.right "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.head = TreeNode(0)\n",
    "        self.res = self.head \n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        def dfs(root): \n",
    "            if not root: \n",
    "                return None \n",
    "            dfs(root.left)\n",
    "            root.left = None \n",
    "            self.head.right = root\n",
    "            self.head = self.head.right \n",
    "            dfs(root.right)\n",
    "        \n",
    "        dfs(root)\n",
    "        return self.res.right "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        dummy = TreeNode(None)\n",
    "        pre = dummy\n",
    "\n",
    "        # 中序遍历\n",
    "        node = root\n",
    "        stack = []\n",
    "        while node or stack:\n",
    "            while node:\n",
    "                stack.append(node)\n",
    "                node = node.left\n",
    "            \n",
    "            if stack:\n",
    "                node = stack.pop()\n",
    "\n",
    "                # 业务逻辑\n",
    "                pre.right = node\n",
    "                node.left = None\n",
    "                pre = node\n",
    "\n",
    "                node = node.right\n",
    "\n",
    "        \n",
    "        return dummy.right\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        self.pre = self.ans = None\n",
    "        if root is None:\n",
    "            return\n",
    "        self.dfs(root)\n",
    "        return self.ans\n",
    "\n",
    "    def dfs(self, root):\n",
    "            if root is None:\n",
    "                return None\n",
    "        \n",
    "            self.dfs(root.left)\n",
    "            root.left = None\n",
    "            if self.pre: self.pre.right = root\n",
    "            if self.pre is None: self.ans = root\n",
    "            self.pre = root\n",
    "            self.dfs(root.right)\n",
    "\n",
    "    \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:return None\n",
    "        left,right = None,None\n",
    "        if root.left:\n",
    "            left = self.convertBiNode(root.left)\n",
    "        if root.right:\n",
    "            right = self.convertBiNode(root.right)\n",
    "        if left:\n",
    "            cur = left\n",
    "            while cur.right:\n",
    "                cur = cur.right\n",
    "            cur.right = root\n",
    "        root.left = None\n",
    "        root.right = right\n",
    "        return left if left else root\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if root is None:\n",
    "            return root\n",
    "        head = pre = None\n",
    "        def dfs(node):\n",
    "            nonlocal pre, head\n",
    "            if node:\n",
    "                dfs(node.left)\n",
    "                if head is None:\n",
    "                    head = node\n",
    "                if pre is not None:\n",
    "                    pre.right = node\n",
    "                    node.left = None\n",
    "                pre = node\n",
    "                dfs(node.right)\n",
    "        dfs(root)\n",
    "        return head"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "            \n",
    "        head = self.convert(root)\n",
    "        return head\n",
    "\n",
    "    def convert(self, root):\n",
    "        # 如果递归的结点是空，则返回None\n",
    "        if not root:\n",
    "            return None\n",
    "\n",
    "        if not (root.right or root.left):\n",
    "            return root\n",
    "\n",
    "        # 默认返回值为递归到的结点    \n",
    "        head = root\n",
    "        \n",
    "        # 如果有左孩子\n",
    "        if root.left:\n",
    "            # 得到左子树的头\n",
    "            left = self.convert(root.left)\n",
    "            head = left\n",
    "            # 得到左子树的尾\n",
    "            while left.right:\n",
    "                left = left.right\n",
    "            # 连接（1）\n",
    "            left.right = root\n",
    "        \n",
    "        # 如果有右孩子\n",
    "        if root.right:\n",
    "            # 得到右子树的头\n",
    "            right = self.convert(root.right)\n",
    "            # 连接（2）\n",
    "            root.right = right\n",
    "        \n",
    "        root.left = None\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.cur = TreeNode()\n",
    "        self.res = self.cur\n",
    "\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:return None\n",
    "        self.convertBiNode(root.left)\n",
    "        root.left=None\n",
    "        self.cur.right = root\n",
    "        self.cur = self.cur.right\n",
    "        self.convertBiNode(root.right)\n",
    "        return self.res.right\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        if not root:\n",
    "            return None\n",
    "            \n",
    "        head = self.convert(root)\n",
    "        return head\n",
    "\n",
    "    def convert(self, root):\n",
    "        if not root:\n",
    "            return None\n",
    "            \n",
    "        head = root\n",
    "        \n",
    "        if root.left:\n",
    "            left = self.convert(root.left)\n",
    "            head = left\n",
    "            while left.right:\n",
    "                left = left.right\n",
    "            left.right = root\n",
    "        \n",
    "        if root.right:\n",
    "            right = self.convert(root.right)\n",
    "            root.right = right\n",
    "        \n",
    "        root.left = None\n",
    "        return head\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# Definition for a binary tree node.\n",
    "# class TreeNode:\n",
    "#     def __init__(self, x):\n",
    "#         self.val = x\n",
    "#         self.left = None\n",
    "#         self.right = None\n",
    "\n",
    "class Solution:\n",
    "    def solve(self, root: TreeNode) -> (TreeNode, TreeNode):\n",
    "        if root is None:\n",
    "            return None, None\n",
    "        print(root.val)\n",
    "        if root.left is None and root.right is None:\n",
    "            return root,root\n",
    "        h1, e1, = self.solve(root.left)\n",
    "        h2, e2 = self.solve(root.right)\n",
    "        #return h1, e2\n",
    "        if h1 is not None:\n",
    "            h1.left = None\n",
    "            e1.left = None\n",
    "            e1.right = root\n",
    "        if h2 is not None:\n",
    "            h2.left = None\n",
    "            e2.left = None\n",
    "            root.right = h2\n",
    "        root.left = None\n",
    "        h, e = None, None\n",
    "        if h1 is not None:\n",
    "            h = h1\n",
    "        else:\n",
    "            h = root\n",
    "        if h2 is not None:\n",
    "            e = e2\n",
    "        else:\n",
    "            e = root\n",
    "            root.right = None\n",
    "        return h,e\n",
    "        \n",
    "    def convertBiNode(self, root: TreeNode) -> TreeNode:\n",
    "        h, _ = self.solve(root)\n",
    "        return h"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
